package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author kaho
 * @since 2021/2/20
 */
public class _95_不同的二叉搜索树_II {

    /**
     *给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
     * @param n
     * @return
     */
    public static List<TreeNode> generateTrees3(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }

        return dfs3(1, n);
    }

    private static List<TreeNode> dfs3(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (start>end) {
            result.add(null);
            return result;
        }
        if (start == end) {
            result.add(new TreeNode(start));
            return result;
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> left = dfs3(start, i - 1);
            List<TreeNode> right = dfs(i + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    result.add(root);
                }
            }

        }
        return result;
    }


    public static List<TreeNode> generateTrees(int n) {
        List<TreeNode> result = new ArrayList<>();
        if (n ==0) {
            return result;
        }
        return dfs(1,n);
    }

    private static List<TreeNode> dfs(int i, int n) {
        List<TreeNode> cur = new ArrayList<>();
        if (i>n) {
            cur.add(null);
            return cur;
        }
        if (i == n) {
            cur.add(new TreeNode(i));
            return cur;
        }
        for (int i1 = i; i1 <= n; i1++) {
            List<TreeNode> left = dfs(i, i1 - 1);
            List<TreeNode> right = dfs(i1+1, n);
            for (TreeNode leftNode : left) {
                for (TreeNode rightNode : right) {
                    TreeNode root = new TreeNode(i1);
                    root.left = leftNode;
                    root.right = rightNode;
                    cur.add(root);
                }
            }
        }
        return cur;
    }


    public static List<TreeNode> generateTrees1(int n) {
        List<TreeNode> result = new ArrayList<>();
        if (n == 0) {
            return result;
        }
        return doGenerate(1,n);
    }

    private static List<TreeNode> doGenerate(int begin, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (begin>end) {
            result.add(null);
            return result;
        }
        if (begin == end) {
            TreeNode root = new TreeNode(begin);
            result.add(root);
            return result;
        }

        for (int i = begin; i <= end; i++) {
            List<TreeNode> lefts = doGenerate(begin, i-1);
            List<TreeNode> rights = doGenerate(i+1, end);

            for (TreeNode left : lefts) {
                for (TreeNode right : rights) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }
        return result;
    }


    public static List<TreeNode> generateTrees2(int n) {
        List<TreeNode> ans = new ArrayList<TreeNode>();
        if (n == 0) {
            return ans;
        }
        return getAns(1, n);

    }

    private static List<TreeNode> getAns(int start, int end) {
        List<TreeNode> ans = new ArrayList<TreeNode>();
        //此时没有数字，将 null 加入结果中
        if (start > end) {
            ans.add(null);
            return ans;
        }
        //只有一个数字，当前数字作为一棵树加入结果中
        if (start == end) {
            TreeNode tree = new TreeNode(start);
            ans.add(tree);
            return ans;
        }
        //尝试每个数字作为根节点
        for (int i = start; i <= end; i++) {
            //得到所有可能的左子树
            List<TreeNode> leftTrees = getAns(start, i - 1);
            //得到所有可能的右子树
            List<TreeNode> rightTrees = getAns(i + 1, end);
            //左子树右子树两两组合
            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    //加入到最终结果中
                    ans.add(root);
                }
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        List<TreeNode> treeNodes = generateTrees(3);
    }
}
